﻿/*
 * sparce_color.hpp
 *
 *  Created on: 2020年2月23日
 *      Author: Dylan.Gao
 */

#ifndef _DM_SPARCE_COLOR_HPP_
#define _DM_SPARCE_COLOR_HPP_

#include <dm/link_next_simple.hpp>

namespace dm{

/**
 * 稀疏着色
 */
template<typename TKey>
class TCSparceColor{
public:
	typedef TCLinkNextSimple<TKey> list_t;

	TCSparceColor():m_l(NULL){}
	~TCSparceColor(){
		if( m_l )
			delete m_l;
	}

	/**
	 * 增加键值
	 * @param k
	 * @return
	 * - true 成功
	 * - false 失败，已经存在
	 */
	bool add( const TKey& k ){
		list_t* l = findPre(k,m_l);
		if( l ){
			if( l->next() && l->next()->get()==k )
				return false;	// 已经存在
			l->insert(k);
			return true;
		}
		if( m_l ){
			if( m_l->get()==k )
				return false;	// 已经存在

			m_l = m_l->pushHead(k);
		}else
			m_l = new list_t(k);

		return true;
	}

	/**
	 * 查找键值是否存在
	 * @param k
	 * @return
	 */
	bool find( const TKey& k )const{
		const list_t* l = findPre(k,m_l);
		if( l && l->next() && l->next()->get()==k )
			return true;

		if( m_l && m_l->get()==k )
			return true;

		return false;
	}

	bool del( const TKey& k ){
		list_t* l = findPre(k,m_l);
		if( l ){
			if( l->next() && l->next()->get()==k ){
				l->removeNext();
				return true;
			}else{
				return false;	// 不存在
			}
		}

		if( m_l && m_l->get()==k ){
			m_l = m_l->popNexts();
			return true;
		}

		return false;
	}

	inline unsigned int size()const{
		if( m_l )
			return m_l->size();
		else
			return 0;
	}

	const TKey& getByIndex( const unsigned int& idx )const{
		const list_t* l = m_l;
		for( unsigned int i=0;i<idx;++i )
			l = l->next();
		return l->get();
	}

	inline void clear(){
		if( m_l ){
			delete m_l;
			m_l = NULL;
		}
	}
private:
	/**
	 * 查找可作为前一个的节点
	 * @param k
	 * @param l
	 * @return
	 * - NULL 不存在前一个节点
	 */
	template<typename TList>
	TList findPre( const TKey& k,TList l )const{
		if( l==NULL || l->get() >= k )
			return NULL;

		while( l ){
			if( l->next()==NULL || l->next()->get()>=k )
				return l;
			l = l->next();
		}

		return NULL;
	}

private:
	list_t* m_l;
};

}

#endif /* INCLUDE_DM_SPARCE_COLOR_HPP_ */
